
public class Day14 {
    public static void main(String[] args) {
        System.out.println("tmie:fafawfasef");
    }

    public void reorderList(ListNode head) {
        if(head.next == null || head.next.next == null) return;

        //1.先找到中间节点
        ListNode slow = head;
        ListNode fast = head;
        while( fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        //2.拆分成两个链表
        ListNode h = slow.next;
        slow.next = null;
        //3.倒置第二个链表
        if(h.next != null) {
            ListNode cur = h.next;
            h.next = null;
            while(cur != null) {
                ListNode tmp = cur;
                cur = cur.next;
                tmp.next = h;
                h = tmp;
            }
        }
        //4.合并
        //head 和 h
        ListNode cur1 = head;
        ListNode cur2 = h;
        ListNode ret = new ListNode(0);//虚拟头结点
        ListNode prev = ret;
        while(cur1 != null) {
            prev.next = cur1;
            prev = cur1;
            cur1 = cur1.next;

            if(cur2 != null) {
                prev.next = cur2;
                prev = cur2;
                cur2 = cur2.next;
            }
        }
        head = ret.next;
    }
}
